<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  
  
  <link rel="shortcut icon" href="../../img/favicon.ico">
  <title>Event Queues - COROS Documentation</title>
  <link rel="stylesheet" href="../../css/theme.css" />
  <link rel="stylesheet" href="../../css/theme_extra.css" />
  <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/styles/github.min.css" />
  
  <script>
    // Current page data
    var mkdocs_page_name = "Event Queues";
    var mkdocs_page_input_path = "architecture/02_event_queues.md";
    var mkdocs_page_url = null;
  </script>
  
  <script src="../../js/jquery-2.1.1.min.js" defer></script>
  <script src="../../js/modernizr-2.8.3.min.js" defer></script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/highlight.min.js"></script>
  <script>hljs.initHighlightingOnLoad();</script> 
  
</head>

<body class="wy-body-for-nav" role="document">

  <div class="wy-grid-for-nav">

    
    <nav data-toggle="wy-nav-shift" class="wy-nav-side stickynav">
    <div class="wy-side-scroll">
      <div class="wy-side-nav-search">
        <a href="../.." class="icon icon-home"> COROS Documentation</a>
        <div role="search">
  <form id ="rtd-search-form" class="wy-form" action="../../search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" title="Type search term here" />
  </form>
</div>
      </div>

      <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../..">Home</a>
                    </li>
                </ul>
                <p class="caption"><span class="caption-text">About</span></p>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../../COPYRIGHT/">Copyright</a>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../../LICENSE/">License</a>
                    </li>
                </ul>
                <p class="caption"><span class="caption-text">The Beginner's Guide to:</span></p>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../../tutorials/01_getting_started/">Getting Started</a>
                    </li>
                </ul>
                <p class="caption"><span class="caption-text">The Hitchker's Guide to:</span></p>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../../guides/01_coroutines/">Coroutines</a>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../../guides/02_event_queues/">Event Queues</a>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../../guides/03_components/">Components</a>
                    </li>
                </ul>
                <p class="caption"><span class="caption-text">The Technocrat's Guide to:</span></p>
                <ul>
                    <li class="toctree-l1"><a class="reference internal" href="../../reference/01_co/">co.h</a>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../../reference/02_evq/">evq.h</a>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../../reference/03_comp/">comp.h</a>
                    </li>
                </ul>
                <p class="caption"><span class="caption-text">The Technomancer's Guide to:</span></p>
                <ul class="current">
                    <li class="toctree-l1"><a class="reference internal" href="../01_coroutines/">Coroutines</a>
                    </li>
                    <li class="toctree-l1 current"><a class="reference internal current" href="./">Event Queues</a>
    <ul class="current">
    <li class="toctree-l2"><a class="reference internal" href="#events">Events</a>
        <ul>
    <li class="toctree-l3"><a class="reference internal" href="#timing">Timing</a>
    </li>
    <li class="toctree-l3"><a class="reference internal" href="#callback">Callback</a>
    </li>
    <li class="toctree-l3"><a class="reference internal" href="#chaining">Chaining</a>
    </li>
    <li class="toctree-l3"><a class="reference internal" href="#book-keeping">Book-keeping</a>
    </li>
        </ul>
    </li>
    <li class="toctree-l2"><a class="reference internal" href="#event-queues">Event Queues</a>
        <ul>
    <li class="toctree-l3"><a class="reference internal" href="#events_1">Events</a>
    </li>
    <li class="toctree-l3"><a class="reference internal" href="#structure">Structure</a>
        <ul>
    <li class="toctree-l4"><a class="reference internal" href="#child-insertion">Child insertion</a>
    </li>
    <li class="toctree-l4"><a class="reference internal" href="#child-removal">Child removal</a>
    </li>
    <li class="toctree-l4"><a class="reference internal" href="#navigating-the-tree">Navigating the tree</a>
    </li>
        </ul>
    </li>
        </ul>
    </li>
    </ul>
                    </li>
                    <li class="toctree-l1"><a class="reference internal" href="../03_porting/">Porting</a>
                    </li>
                </ul>
      </div>
    </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">

      
      <nav class="wy-nav-top" role="navigation" aria-label="top navigation">
        <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
        <a href="../..">COROS Documentation</a>
      </nav>

      
      <div class="wy-nav-content">
        <div class="rst-content">
          <div role="navigation" aria-label="breadcrumbs navigation">
  <ul class="wy-breadcrumbs">
    <li><a href="../..">Docs</a> &raquo;</li>
    
      
        
          <li>The Technomancer's Guide to: &raquo;</li>
        
      
    
    <li>Event Queues</li>
    <li class="wy-breadcrumbs-aside">
      
    </li>
  </ul>
  
  <hr/>
</div>
          <div role="main">
            <div class="section">
              
                <h1 id="the-technomancers-guide-to-event-queues">The Technomancer's Guide to Event Queues</h1>
<p>Event queues, possibly moreso than even coroutines, likely, are at the heart of what makes COROS a solid architecture for embedded systems.  It is thus likely users will want to know about its architecture in greater detail.</p>
<p>There are two elements which form EVQ: events, and event queues.  How these interact requires a bit of poking around at the innards.</p>
<h2 id="events">Events</h2>
<p>Under the covers, this is what an event looks like:</p>
<pre><code class="language-C">typedef struct _evq_event_t
{
    // timing
    tick_ms  trigger_time;
    delay_ms period;

    // callback
    bool is_coroutine;
    void *data;
    union
    {
        evq_callback cb;
        co_t         co;
    };

    // chaining
    evq_event_t chain;
    evq_queue_t container;

    // book-keeping
    bool reusable;
    bool in_use;
} evq_event_t_impl;
</code></pre>
<p>The members are divided into roughly four pieces, each of which will be treated individually with explanations below.</p>
<h3 id="timing">Timing</h3>
<p>Timing-related members are used to establish the tick the event is intended to activate upon, and the period of activations for repeating events.  They are set when an event is created thusly:</p>
<pre><code class="language-C">    e-&gt;trigger_time = evq_get_tick() + delay;
    e-&gt;period = period;
</code></pre>
<p>Keeping in mind that <code>delay</code> and <code>period</code> are passed in to the low-level API <code>create</code> and <code>fill</code> functions, under the covers the <code>trigger_time</code> is calculated by taking the current tick and adding to it the current delay.  Thus a <code>now</code> function from the high-level API will pass in <code>0</code> and cause the event to be activated as soon as the processor is next run.  The <code>period</code> passed in is just stored.</p>
<p>Events are processed like this.</p>
<p>First, we decide if the event is going to activate:</p>
<pre><code class="language-C">    if (e-&gt;trigger_time &lt;= current)
    {
</code></pre>
<p>We then store information we need to actually call the event.  Why do it this way instead of working off of the event data directly?  Because if we don't, we either have horribly complicated conditional logic that will be buggy as Hell, or we have SRAM being shot with pointers that throw its viscera all over your nice, tidy project.</p>
<pre><code class="language-C">        bool is_coroutine = e-&gt;is_coroutine;
        evq_callback cb = e-&gt;cb;        // cb and co are the same piece of data
        co_t co = e-&gt;co;                // but it's more convenient this way
        void *data = e-&gt;data;
        evq_queue_t cq = e-&gt;container;
</code></pre>
<p>And then we pass over some stuff to get to the part where the event is activated.  Here we check if the event is a coroutine event, in which case we resume the coroutine with the passed-in data, or if it's a callback event, in which case we call the supplied function, passing in the data.</p>
<pre><code class="language-C">        if (is_coroutine)
        {
            co_resume(co, data);
        }
        else
        {
            cb(data);
        }
    }
</code></pre>
<p>So what did we elide?  We elided the part that's relevant to the timing (and the part that causes the occasional SRAM guts blowing all over your project).</p>
<p>First we check for a periodic event, and if it is such, execute this, to recalculate the trigger_time and re-insert the event at a new time.</p>
<pre><code class="language-C">        if (e-&gt;period &gt; 0)
        {
            remove_event(cq, e);
            e-&gt;trigger_time = current + e-&gt;period;
            insert_event(cq, e);
        }
</code></pre>
<p>If it is not that, however, we remove the event, and if it's not a reusable one (most events and all of the high-level ones) we delete the event.</p>
<pre><code class="language-C">        else
        {
            remove_event(cq, e);

            if (!e-&gt;reusable)
            {
                DEL_EVENT(e);
                deallocate_evq_event_t_impl(e);
            }
        }
</code></pre>
<p>This elided material is why we store the contents first, then activate the event.  Removing the event before we activate it means the event will point off into Neverland, spreading SRAM viscera all over the place, or the processing of said event will result in a recursive call back into the processor and cause even WORSE visceral explosion.</p>
<p>But here the big mystery of how events are processed is revealed.  While processing the queue we check events and execute the above code.</p>
<h3 id="callback">Callback</h3>
<pre><code class="language-C">    bool is_coroutine;
    void *data;
    union
    {
        evq_callback cb;
        co_t         co;
    };
</code></pre>
<p>The data for the callback is simplicity itself.  The data pointer is stored.  A union holds either the function pointer for the callback or the coroutine.  A boolean flag decides which is which.  The flag is set by the appropriate <code>create</code> functions as is the union with the callback function/coroutine.  As you saw in the timing section above, using it is itself simplicity.</p>
<h3 id="chaining">Chaining</h3>
<p>This gets a little bit hairier, but only a bit.</p>
<pre><code class="language-C">    // chaining
    evq_event_t chain;
    evq_queue_t container;
</code></pre>
<p>Events are stored in a unidirectional, <code>NULL</code>-terminated linked list.  Event queues (for which q.v.) store a link to the first event in their chain.  Events themselves store the next link.  Also stored is the queue which contains the event for the specific purposes of easing the insertion and removal of events.  This will be addressed more in the discussion of event queues proper.</p>
<h3 id="book-keeping">Book-keeping</h3>
<pre><code class="language-C">    bool reusable;
    bool in_use;
</code></pre>
<p>Reusable events are either periodic ones or ones created with the low-level interface.  They are not deleted automatically by the system upon activation and must be instead destroyed manually.</p>
<p>In-use events are events actively in a queue.  This is used internally for purposes of the debugging counters in the system.</p>
<h2 id="event-queues">Event Queues</h2>
<p>Under the covers, this is what an event queue looks like:</p>
<pre><code class="language-C">typedef struct _evq_queue_t
{
    // structure
    evq_queue_t first_child, next_sibling, parent;

    // events
    evq_event_t head;

    // operations
    bool running;
    evq_idle idle;
} evq_queue_t_impl;
</code></pre>
<p>At first glance this seems a lot simpler than events, but the devil is in the details.  So lets look at those.</p>
<h3 id="events_1">Events</h3>
<p>Every queue has a linked list of events.  The head (first event) of that list is stored in the <code>head</code> member.  Processing the queue looks like this:</p>
<pre><code class="language-C">    evq_event_t e = q-&gt;head;

    while (q-&gt;running &amp;&amp; e)
    {
        evq_event_t n = e-&gt;chain;

        if (e-&gt;trigger_time &lt;= current)
        {
            // ELIDED BECAUSE IT'S IN THE TIMING SECTION OF EVENT DOCUMENTATION
        }
        else
        {
            // All further events are not yet due.
            break;
        }

        e = n;
    }
</code></pre>
<p>It's a simple and straightforward linear traversal of the event queue that ...</p>
<p><em>*RECORD SCRATCH*</em></p>
<p>What?  A <em>linear search</em>!?  As in O(n)?!</p>
<p>Yes.  It's a linear search.  Thus far there has been no need to explore other options like using multiple chains organized by time or such.  The fact we cut down the search by a) ordering the events in time order, and b) truncating the search as soon as the trigger time exceeds the current time, means that there's not a lot of events ready for processing at any given moment.  High water mark measurements on live systems using these macros...</p>
<pre><code class="language-C">// debugging statistics
static size_t debug_queues, debug_queue_entries, debug_callback_events, debug_coroutine_events, debug_events;
#define ADD_QUEUE() do { ++debug_queues; } while (false)
#define ADD_QUEUE_ENTRY() do { ++debug_queue_entries; } while (false)
#define DEL_QUEUE_ENTRY() do { --debug_queue_entries; } while (false)
#define ADD_FN_EVENT() do { ++debug_callback_events; ++debug_events; } while (false)
#define DEL_FN_EVENT() do { --debug_callback_events; --debug_events; } while (false)
#define ADD_CO_EVENT() do { ++debug_coroutine_events; ++debug_events; } while (false)
#define DEL_CO_EVENT() do { --debug_coroutine_events; --debug_events; } while (false)
#define DEL_EVENT(E) do { if (E-&gt;is_coroutine) DEL_CO_EVENT(); else DEL_FN_EVENT(); } while (false)
</code></pre>
<p>...show that rarely are there more than a dozen events live at any given moment.  So let's look at how this optimization works:</p>
<pre><code class="language-C">static inline void insert_event(evq_queue_t q, evq_event_t e)
{
    assert(q != NULL);
    assert(e != NULL);

    if (!q-&gt;head || (q-&gt;head-&gt;trigger_time &gt; e-&gt;trigger_time))
    {
        // We're the first event in this evq_queue_t.
        e-&gt;chain = q-&gt;head;
        q-&gt;head = e;
        ADD_QUEUE_ENTRY();
    }
    else
    {
        evq_event_t c = q-&gt;head;

        do
        {
            evq_event_t n = c-&gt;chain;

            if (!n || n-&gt;trigger_time &gt; e-&gt;trigger_time)
            {
                c-&gt;chain = e;
                e-&gt;chain = n;
                ADD_QUEUE_ENTRY();
                break;
            }

            c = n;
        }
        while (c);
    }
}
</code></pre>
<p>As you can see, we just walk the chain until we either hit the end, or we hit an event whose trigger time is greater than ours.  At this point we insert the new event.  Easy peasy lemon squ...</p>
<p><em>*RECORD SCRATCH*</em></p>
<p>What?  A <em>linear insertion</em>!?  As in O(n)?!</p>
<p><em>&lt;sigh></em></p>
<p>Yes.  A linear insertion.  Again, real world measurements have shown this is not an issue.  Events are inspected and possibly activated several orders of magnitude more times than they are inserted.  Profiling shows that event insertion barely registers as a system overhead.</p>
<p>So a fairly uncommon operation is fully linear without a quick bailout.  The most common single such operation is linear but with a quick backout.  It works.</p>
<blockquote>
<p><em><strong>A note on design philosophy:</strong> In embedded systems, the "best" algorithm isn't necessarily the one with the best theoretical complexity, but the one that plays nicest with your hardware constraints.  Linear scans of small, ordered lists are often optimal because they're cache-friendly, branch-predictable, and simple enough to be obviously correct.  It's often better to do the simple thing and </em>measure<em> rather than reach immediately for the fancy stuff.</em></p>
<p><em>This philosophy is not advocacy for blindly simple code, mind you.  For example events are allocated with an object pool allocation system because using malloc() and free() for them led to heap fragmentation to the point events couldn't be allocated and the system ground to a halt.  In its place a sophisticated boutique allocation system was concocted and put into place.  This is why you </em>start<em> simple and correct, and then escalate the complexity and cleverness when the simplicity is </em><em>proved</em><em> insufficient to the task.</em></p>
</blockquote>
<h3 id="structure">Structure</h3>
<p>Repeating the relevant portions from the structure we have this:</p>
<pre><code class="language-C">    evq_queue_t first_child, next_sibling, parent;
</code></pre>
<p>A single line declaring three members of the structure.  Yet these three variables are behind the whole tree structuring that makes EVQ if not unique, certainly fairly rare in the field of event processing.</p>
<p>As has been stated over and again in the documentation, EVQ is &lt;refrain>a tree structured event queue system&lt;/refrain>.  It is, however, for reasons of memory localization, a tree structure in which nodes are also the leafs.</p>
<p>So let's talk about the first queue created, which we will refer to as the main queue for this discussion.  When a queue is created, it has <code>NULL</code> for its <code>first_child</code>, its <code>parent</code>, and its <code>next_sibling</code>.  (A main queue is, in fact, by convention, one which has no siblings nor a parent.  This has repercussions which the advanced usage section of <a href="../../guides/02_event_queues/"><em>The Hitchhiker's Guide to Event Queues</em></a> covers, to wit that there can be more than one "main queue" in a system.)</p>
<h4 id="child-insertion">Child insertion</h4>
<p>This main queue can stand alone (and for simple systems may well be all that's needed).  But once a child is inserted, things get a little bit more involved:</p>
<pre><code class="language-C">static inline void insert_child(evq_queue_t p, evq_queue_t c)
{
    evq_queue_t s = p-&gt;first_child;
    if (s != NULL)
    {
        while (s-&gt;next_sibling != NULL)
        {
            s = s-&gt;next_sibling;
        }
        s-&gt;next_sibling = c;
    }
    else
    {
        p-&gt;first_child = c;
    }
}
</code></pre>
<p>The actual insertion is simple.  If the parent queue doesn't have a <code>first_child</code> the child queue is now the <code>first_child</code>.  Otherwise the routine starts walking the children's <code>next_sibling</code> chain until it sees NULL.  At this point the child is linked to the tail of the chain.</p>
<h4 id="child-removal">Child removal</h4>
<p>Removing is a bit more involved:</p>
<pre><code class="language-C">    // if we don't have a parent we're already a detached root
    evq_queue_t parent = q-&gt;parent;
    if (parent)
    {
</code></pre>
<p>First we check if we have a parent.  By definition if there is no parent we are already a tree root (main queue).</p>
<p>If we have a parent, however:</p>
<pre><code class="language-C">        evq_queue_t sibling = parent-&gt;first_child;

        // we're the first child, so point to the next
        if (sibling == q)
        {
            parent-&gt;first_child = q-&gt;next_sibling;
        }
</code></pre>
<p>If we're the first child, we just replace the first child with the next sibling.  Otherwise...</p>
<pre><code class="language-C">        else
        {
            // otherwise find our place and pull out of the list
            while (sibling)
            {
                if (sibling-&gt;next_sibling == q)
                {
                    sibling-&gt;next_sibling = q-&gt;next_sibling;
                    break;
                }
                sibling = sibling-&gt;next_sibling;
            }
        }
    }
</code></pre>
<p>... we search through all the parent's children until the queue being removed has been found.  At this point we unlike ourselves from the sibling chain.</p>
<p>When all this is completed we have a standalone event queue tree root.  We remove our sibling and our parent.</p>
<pre><code class="language-C">    // upon detachment we no longer have a parent nor a sibling
    q-&gt;next_sibling = NULL;
    q-&gt;parent = NULL;
}
</code></pre>
<h4 id="navigating-the-tree">Navigating the tree</h4>
<p>This is all just the warm-up to the main event: navigating a queue tree to find and activate messages.</p>
<p>First we look at inserting an event:</p>
<pre><code class="language-C">    if (!q-&gt;head || (q-&gt;head-&gt;trigger_time &gt; e-&gt;trigger_time))
    {
        // We're the first event in this evq_queue_t.
        e-&gt;chain = q-&gt;head;
        q-&gt;head = e;
        ADD_QUEUE_ENTRY();
    }
</code></pre>
<p>The simplest case is that the queue has no events.  In this case we just put our event as the head.  Otherwise we have to find our place in the queue.</p>
<pre><code class="language-C">    else
    {
        evq_event_t c = q-&gt;head;

        do
        {
            evq_event_t n = c-&gt;chain;

            if (!n || n-&gt;trigger_time &gt; e-&gt;trigger_time)
            {
                c-&gt;chain = e;
                e-&gt;chain = n;
                ADD_QUEUE_ENTRY();
                break;
            }

            c = n;
        }
        while (c);
    }
}
</code></pre>
<p>Removal of an event follows similar logic and won't be detailed here.  Instead we will look at event processing logic.  We have already seen how the queue searches its own events above.  Here is instead how the children are visited.</p>
<pre><code class="language-C">    evq_queue_t child = q-&gt;first_child;
    while (child)
    {
        child-&gt;running = true;
        process_queue(child, current);
        child-&gt;running = false;
        child = child-&gt;next_sibling;
    }
</code></pre>
<p>It really is that simple.</p>
<p>Once, however, all local events and and children are processed, there is one last step: dealing with any idle functions that may be active:</p>
<pre><code class="language-C">    do
    {
        if (q-&gt;idle)        { q-&gt;idle(); break; }
        else if (q-&gt;parent) { q = q-&gt;parent;    }
        else                { break;            }
    } while (q);
</code></pre>
<p>If the current queue has an idle function set, we call it and exit.  Otherwise we move up the parental chain testing for idle functions until we either hit the root or find and idle function.</p>
<p>And this is how all event processing is done.  Involved but not incomprehensible.</p>
              
            </div>
          </div>
          <footer>
  
    <div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
      
        <a href="../03_porting/" class="btn btn-neutral float-right" title="Porting">Next <span class="icon icon-circle-arrow-right"></span></a>
      
      
        <a href="../01_coroutines/" class="btn btn-neutral" title="Coroutines"><span class="icon icon-circle-arrow-left"></span> Previous</a>
      
    </div>
  

  <hr/>

  <div role="contentinfo">
    <!-- Copyright etc -->
    
  </div>

  Built with <a href="https://www.mkdocs.org/">MkDocs</a> using a <a href="https://github.com/snide/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>.
</footer>
      
        </div>
      </div>

    </section>

  </div>

  <div class="rst-versions" role="note" aria-label="versions">
    <span class="rst-current-version" data-toggle="rst-current-version">
      
      
        <span><a href="../01_coroutines/" style="color: #fcfcfc;">&laquo; Previous</a></span>
      
      
        <span style="margin-left: 15px"><a href="../03_porting/" style="color: #fcfcfc">Next &raquo;</a></span>
      
    </span>
</div>
    <script>var base_url = '../..';</script>
    <script src="../../js/theme.js" defer></script>
      <script src="../../search/main.js" defer></script>
    <script defer>
        window.onload = function () {
            SphinxRtdTheme.Navigation.enable(true);
        };
    </script>

</body>
</html>
